package cn.fxzhang.leetcode.contest.lccup2021;

/**
 * LCP 33 蓄水
 *
 * 类型：枚举/数学
 * 题解：枚举蓄水次数，根据该次数，计算每个桶要增加多少容量，累计起来即可
 * 时间复杂度：O(max(vat[i])*n), 水缸最大容量*水缸数量
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 9 ms
 * 内存消耗: 36.1 MB
 *
 * 【中等】通过次数899 提交次数10,740
 * @author 张晓帆
 * @date 2021/4/10
 */
public class LCP_33 {

    public int storeWater(int[] bucket, int[] vat) {
        int maxVat = 0;
        int len = bucket.length;
        for (int i = 0; i < vat.length; i++){
            maxVat = Math.max(vat[i], maxVat);
        }
        if (maxVat == 0){
            return 0;
        }
        // 假设每个桶的容量都是0，每个桶容量加1
        int ans = len+maxVat;
        // 枚举需要蓄水的次数
        for (int i=1; i<=maxVat&&i<ans; i++){
            int tmp = i;
            // 累计每个桶要加多少次水
            for (int j=0; j<bucket.length&&tmp<ans; j++){
                tmp = tmp + Math.max((int)Math.ceil(vat[j]*1.0/i)-bucket[j], 0);
            }
            ans = Math.min(tmp, ans);
        }
        return ans;
    }
}
